πŸ‘©β€πŸ’» 64064. λΆˆλŸ‰ μ‚¬μš©μž

@Seongukbaek Posted May 12, 2022 Β· Updated May 12, 2022 Β· 2 min read

문제

Programmers - λΆˆλŸ‰ μ‚¬μš©μž

πŸ“ Logic

public void findBadUser(HashSet<String> set, int size) { if (size == bannedIdList.size()) { banSet.add(new HashSet<>(set)); return; } // list번째 제재 아이디λ₯Ό set에 μΆ”κ°€ for (String id : bannedIdList.get(size)) { if (set.contains(id)) continue; set.add(id); findBadUser(set, size + 1); set.remove(id); } }
  • DFS λ°©μ‹μœΌλ‘œ 제재 아이디 set 을 μƒμ„±ν•˜κ³ , 이λ₯Ό 쀑볡이 없도둝 ν•˜κΈ° μœ„ν•΄ HashSet 에 μ €μž₯ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; import java.util.regex.Pattern; class Ban { HashSet<HashSet<String>> banSet; ArrayList<ArrayList<String>> bannedIdList; public Ban() { banSet = new HashSet<>(); bannedIdList = new ArrayList<>(); } public void makeSet(String banned_id, String[] user_id) { // μ •κ·œν‘œν˜„μ‹ μ‚¬μš©μ„ μœ„ν•΄ λ³€ν™˜ String regex = banned_id.replace('*', '.'); ArrayList<String> tmpList = new ArrayList<>(); for (String user : user_id) { boolean isMatch = Pattern.matches(regex, user); if (isMatch) tmpList.add(user); } bannedIdList.add(tmpList); } public void findBadUser(HashSet<String> set, int size) { if (size == bannedIdList.size()) { banSet.add(new HashSet<>(set)); return; } // list번째 제재 아이디λ₯Ό set에 μΆ”κ°€ for (String id : bannedIdList.get(size)) { if (set.contains(id)) continue; set.add(id); findBadUser(set, size + 1); set.remove(id); } } public int getCount() { return banSet.size(); } } class Solution { public int solution(String[] user_id, String[] banned_id) { Ban b = new Ban(); for (String ban : banned_id) b.makeSet(ban, user_id); b.findBadUser(new HashSet<>(), 0); return b.getCount(); } }

✏️ Review

  • μ •κ·œ ν‘œν˜„μ‹λ§ŒμœΌλ‘œ ν•΄κ²°ν•˜λ €κ³  ν–ˆμ§€λ§Œ, DFS λ°©μ‹μœΌλ‘œ 쀑볡을 ν™•μΈν•˜λŠ” 과정이 ν•„μš”ν–ˆλ‹€.
  • 이런 μœ ν˜•μ˜ DFS, BFS λ°©μ‹μ˜ λ¬Έμ œλ„ μžˆμ„ 수 μžˆλ‹€λŠ” 것을 μ•Œκ²Œ λ˜μ—ˆλ‹€.
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€